//目标和
//测试链接：https://leetcode.cn/problems/target-sum/
public class FindTargetSumWays {
    int ans = 0; //记录成功的数目
    int path = 0; //记录每一次的结果
    int target = 0;
    public int findTargetSumWays(int[] nums, int _target) {
        target = _target;
        dfs(nums, 0);
        return ans;
    }

    public void dfs(int[] nums, int pos) {
        if(pos == nums.length) {
            if(path == target) ans++;
            return;
        }

        path = path + nums[pos];
        dfs(nums,pos+1);
        path = path - nums[pos]; //恢复现场

        path = path + (-nums[pos]);
        dfs(nums,pos+1);
        path = path - (-nums[pos]); //恢复现场
    }
}
